var maxProfit = function (k, prices) {
  let n = prices.length;
  if (k > n / 2) {
    k = Math.floor(n / 2); //这样也可以，但其实增加了时间复杂度和内存消耗
    // return maxProfit_k_infinity(prices); //也可以
  }
  let profit = new Array(k);
  //初始化买入卖出时的利润
  for (let j = 0; j <= k; j++) {
    profit[j] = {
      profit_in: -prices[0],
      profit_out: 0,
    };
  }
  for (let i = 0; i < n; i++) {
    for (let j = 1; j <= k; j++) {
      profit[j] = {
        profit_out: Math.max(
          profit[j].profit_out,
          profit[j].profit_in + prices[i]
        ),
        profit_in: Math.max(
          profit[j].profit_in,
          profit[j - 1].profit_out - prices[i]
        ),
      };
    }
  }
  return profit[k].profit_out;
};
